package l.l.w.leetcode._029DivideTwoIntegers;


import java.util.Random;

public class _029DivideTwoIntegers{
    public int divide(int dividend, int divisor) {
        if(divisor == 0) return 0;  //除数为0的话需要抛出异常
        //相等的话直接返回1
        if(divisor == Integer.MIN_VALUE && dividend == Integer.MIN_VALUE) return 1;
        //除数为最小值返回0
        if(divisor == Integer.MIN_VALUE) return 0;
        //被除数为最小值的话，需要其他操作
        //  a / b = (k = (a - 1)/b) + (a - b * k)/b;
        if(dividend == Integer.MIN_VALUE){
            int i = divide1(add(dividend, 1), divisor);
            // 这个判断是leetCode上面的要求，超过最大值的话，直接返回最大值。但是正常情况下越界就越界了吧
            if(i == Integer.MAX_VALUE) return Integer.MAX_VALUE;
            int j = divide1(minus(dividend, multi(divisor, i)), divisor);
            return add(i,j);
        }
        // 其他情况
        return divide1(dividend,divisor);
    }
    private int divide1(int dividend, int divisor){
        // 保存符号，都用正数进行操作，最后根据符号判断结果的正负
        boolean isNegDividend = dividend < 0;
        boolean isNegDivisor = divisor < 0;
        if(isNegDividend){
            dividend = neg(dividend);
        }
        if(isNegDivisor){
            divisor = neg(divisor);
        }
        int i = 31;
        int result = 0;
        for(; i >= 0; --i){
            //判断 除数 最多 左移位多少 之后还小于被除数
            if((dividend >> i) >= divisor){
                //被除数减去除数乘以多少倍
                dividend = minus(dividend,divisor << i);
                result |= (1 << i);//第i位为1
            }
        }
        return (isNegDividend == isNegDivisor)?result : neg(result);
    }

    /**
     * 取相反数
     * @param a
     * @return
     */
    public int neg(int a) {
        // 按位取反，末位加1
        return add(~a, 1);
    }

    /**
     * 减法,利用加法和取相反数
     * @param a
     * @param b
     * @return
     */
    public int minus(int a, int b) {
        return add(a, neg(b));
    }

    /**
     * 减法
     * @param a
     * @param b
     * @return
     */
    public int minusNoUseAdd(int a, int b) {
        while (b != 0){
            int temp = a & b;   //得到减数和被减数都为1的位，相减之后为0
            a = a ^ temp;
            b = b ^ temp;
            a = a ^ b;      //
            b = b << 1;
        }
        return a;
    }
    /**
     * 加法
     * @param a
     * @param b
     * @return
     */
    public int add(int a, int b){
        int sum = 0;
        while(b != 0){
            sum = a ^ b;
            b = a & b;
            a = sum;
            b <<= 1;
        }
        return a;
    }
    /**
     * 乘法
     */
    public int multi(int a, int b){
        boolean isNegA = a < 0;
        boolean isNegB = b < 0;
        if(isNegA){
            a = neg(a);
        }
        if(isNegB){
            b = neg(b);
        }
        int result = 0;
        while( b != 0){
            if((b & 1) != 0){
                result = add(result, a);
            }
            a <<= 1;
            b >>= 1;
        }
        return (isNegA == isNegB)?result : neg(result);
    }
    public static void main(String[] args) {
        _029DivideTwoIntegers solution = new _029DivideTwoIntegers();
        Random random = new Random();
        int a = random.nextInt(10000000);
        int b = random.nextInt(100);
        System.out.println("加法: a = " + a + ", b = " + b);
        System.out.println("" + a + " + " + b + " = " + (a + b));
        System.out.println(solution.add(a, b));
        System.out.println("相反数: a = " + a);
        System.out.println("-a = " + (-a));
        System.out.println(solution.neg(a));
        System.out.println("减法： a = " + a + ", b = " + b);
        System.out.println(solution.minus(a, b));
        System.out.println(""+ a +" - " + b + " = " + (a- b));
        System.out.println(solution.minusNoUseAdd(a, b));
        
        System.out.println("乘法： a = " + a + ", b = " + b);
        System.out.println(solution.multi(a, b));
        System.out.println("" + a + " * "+ b +" = "  + a*b);

        System.out.println("除法： a = " + a + ", b = " + b);
        System.out.println(solution.divide(-2147483648, -3));
        System.out.println("" + a + " / "+ b +" = "  + (-2147483648/(-1)));
    }
}